#define _CRT_SECURE_NO_WARNINGS
//
// 
// 
// 
//#include <iostream>
//#include <vector>
//using namespace std;
//
//vector<int> mul(vector<int> A, int b)
//{
//    vector<int> C;
//    int tmp = 0;
//    for (int i = 0; i < A.size() || tmp; i++)
//    {
//        if (i < A.size()) tmp += A[i] * b;
//        C.push_back(tmp % 10);
//        tmp /= 10;
//    }
//
//    while (C.size() > 1 && C.back() == 0) C.pop_back();
//
//    return C;
//}
//
//int main()
//{
//    string a;
//    int b;
//    cin >> a >> b;
//    vector<int> A;
//
//    for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
//
//    auto C = mul(A, b);
//
//    for (int i = C.size() - 1; i >= 0; i--) cout << C[i];
//    cout << endl;
//
//    return 0;
//}

//
//#include <iostream>
//#include <vector>
//#include <algorithm>
//using namespace std;
//
//vector<int> div(vector<int>& A, int b, int& r)
//{
//    vector<int> C;
//    for (int i = A.size() - 1; i >= 0; i--)
//    {
//        r = r * 10 + A[i];
//        C.push_back(r / b);
//        r %= b;
//    }
//
//    reverse(C.begin(), C.end());
//    while (C.size() > 1 && C.back() == 0) C.pop_back();
//
//    return C;
//}
//
//int main()
//{
//    string a;
//    int b;
//    cin >> a >> b;
//    vector<int> A;
//
//    for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
//
//    int r = 0;
//    auto C = div(A, b, r);
//
//    for (int i = C.size() - 1; i >= 0; i--) cout << C[i];
//    cout << endl << r << endl;
//
//    return 0;
//}

//
//#include <iostream>
//using namespace std;
//
//const int N = 100010;
//int a[N], s[N], n, q;
//
//int main()
//{
//    cin >> n >> q;
//    for (int i = 1; i <= n; i++) cin >> a[i];
//    for (int i = 1; i <= n; i++) s[i] += s[i - 1] + a[i];
//
//    while (q--)
//    {
//        int l, r;
//        cin >> l >> r;
//        cout << s[r] - s[l - 1] << endl;
//    }
//
//    return 0;
//}

//
//#include <iostream>
//using namespace std;
//
//const int N = 1010;
//int n, m, q, a[N][N], s[N][N];
//
//int main()
//{
//    cin >> n >> m >> q;
//    for (int i = 1; i <= n; i++)
//        for (int j = 1; j <= m; j++)
//            cin >> a[i][j];
//
//    for (int i = 1; i <= n; i++)
//        for (int j = 1; j <= m; j++)
//            s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
//
//    while (q--)
//    {
//        int x1, y1, x2, y2;
//        cin >> x1 >> y1 >> x2 >> y2;
//        cout << s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1] << endl;
//    }
//
//    return 0;
//}
//
// 
// 
// 
// 
//#include <iostream>
//using namespace std;
//
//const int N = 100010;
//int n, q, a[N], b[N];
//
//void insert(int l, int r, int c)
//{
//    b[l] += c;
//    b[r + 1] -= c;
//}
//
//int main()
//{
//    cin >> n >> q;
//    for (int i = 1; i <= n; i++) cin >> a[i];
//    for (int i = 1; i <= n; i++) insert(i, i, a[i]);
//
//    while (q--)
//    {
//        int l, r, c;
//        cin >> l >> r >> c;
//        insert(l, r, c);
//    }
//
//    for (int i = 1; i <= n; i++) b[i] += b[i - 1];
//    for (int i = 1; i <= n; i++) cout << b[i] << ' ';
//    cout << endl;
//
//    return 0;
//}


//
//#include <iostream>
//using namespace std;
//
//const int N = 1010;
//int n, m, q, a[N][N], b[N][N];
//
//void insert(int x1, int y1, int x2, int y2, int c)
//{
//    b[x1][y1] += c;
//    b[x1][y2 + 1] -= c;
//    b[x2 + 1][y1] -= c;
//    b[x2 + 1][y2 + 1] += c;
//}
//
//int main()
//{
//    cin >> n >> m >> q;
//    for (int i = 1; i <= n; i++)
//        for (int j = 1; j <= m; j++)
//            cin >> a[i][j];
//
//    for (int i = 1; i <= n; i++)
//        for (int j = 1; j <= m; j++)
//            insert(i, j, i, j, a[i][j]);
//
//    while (q--)
//    {
//        int x1, y1, x2, y2, c;
//        cin >> x1 >> y1 >> x2 >> y2 >> c;
//        insert(x1, y1, x2, y2, c);
//    }
//
//    for (int i = 1; i <= n; i++)
//        for (int j = 1; j <= m; j++)
//            b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];
//
//    for (int i = 1; i <= n; i++)
//    {
//        for (int j = 1; j <= m; j++) cout << b[i][j] << ' ';
//        cout << endl;
//    }
//
//    return 0;
//}

//
//#include <iostream>
//using namespace std;
//
//const int N = 100010;
//int a[N], tmp[N], n;
//
//int main()
//{
//    cin >> n;
//
//    for (int i = 0; i < n; i++) cin >> a[i];
//
//    int max_len = 0;
//    for (int i = 0, j = 0; i < n; i++)
//    {
//        tmp[a[i]] ++;
//        while (tmp[a[i]] > 1) tmp[a[j]] --, j++;
//        max_len = max(max_len, i - j + 1);
//    }
//
//    cout << max_len;
//
//    return 0;
//}

//
//#include <iostream>
//#include <unordered_map>
//using namespace std;
//
//const int N = 100010;
//int n, m, x, a[N], b[N];
//
//int main()
//{
//    unordered_map<int, int> mp;
//
//    cin >> n >> m >> x;
//    for (int i = 0; i < n; i++) cin >> a[i], mp[a[i]] = i;
//    for (int i = 0; i < m; i++) cin >> b[i];
//
//    for (int i = 0; i < m; i++)
//    {
//        int targe = x - b[i];
//        if (mp.count(targe))
//        {
//            cout << mp[targe] << ' ' << i << endl;
//            break;
//        }
//    }
//
//    return 0;
//}

//
//#include <iostream>
//using namespace std;
//
//const int N = 100010;
//int n, m;
//int a[N], b[N];
//
//int main()
//{
//    cin >> n >> m;
//    for (int i = 0; i < n; i++) cin >> a[i];
//    for (int i = 0; i < m; i++) cin >> b[i];
//
//    int l1 = 0, l2 = 0;
//    while (l1 < n && l2 < m)
//    {
//        while (l2 < m && b[l2] != a[l1]) l2++;
//        if (l2 == m) break;
//        l1++;
//        l2++;
//    }
//
//    if (l1 == n || (l1 == n && l2 == m)) cout << "Yes" << endl;
//    else cout << "No" << endl;
//
//    return 0;
//}


//
//#include <iostream>
//using namespace std;
//
//int n;
//
//int lowbit(int x) { return x & -x; }
//
//int main()
//{
//    cin >> n;
//
//    while (n--)
//    {
//        int tmp = 0, count = 0;
//        cin >> tmp;
//        while (tmp) tmp -= lowbit(tmp), count++;
//        cout << count << ' ';
//    }
//    cout << endl;
//
//    return 0;
//}
//
// 
// 
// 
// 
//#include <iostream>
//#include <vector>
//#include <algorithm>
//using namespace std;
//
//const int N = 300010;
//int n, m;
//int a[N], s[N];
//vector<int> alls;
//vector<pair<int, int>> xc, lr;
//
//int find(int x)
//{
//    int l = 0, r = alls.size() - 1;
//    while (l < r)
//    {
//        int mid = (l + r) >> 1;
//        if (alls[mid] >= x) r = mid;
//        else l = mid + 1;
//    }
//
//    return l + 1;
//}
//
//int main()
//{
//    cin >> n >> m;
//    while (n--)
//    {
//        int x, c;
//        cin >> x >> c;
//        alls.push_back(x);
//        xc.push_back({ x, c });
//    }
//
//    while (m--)
//    {
//        int l, r;
//        cin >> l >> r;
//        alls.push_back(l);
//        alls.push_back(r);
//        lr.push_back({ l, r });
//    }
//
//    sort(alls.begin(), alls.end());
//    alls.erase(unique(alls.begin(), alls.end()), alls.end());
//
//    for (auto item : xc)
//    {
//        int i = find(item.first);
//        a[i] += item.second;
//    }
//
//    for (int i = 1; i <= alls.size(); i++) s[i] += s[i - 1] + a[i];
//
//    for (auto item : lr)
//    {
//        int l = find(item.first), r = find(item.second);
//        cout << s[r] - s[l - 1] << endl;
//    }
//
//    return 0;
//}

//
//#include <iostream>
//#include <vector>
//#include <algorithm>
//using namespace std;
//
//int n;
//vector<pair<int, int>> lr;
//
//void merge(vector<pair<int, int>>& res)
//{
//    vector<pair<int, int>> tmp;
//
//    sort(res.begin(), res.end());
//
//    int st = -2e9, ed = -2e9;
//
//    for (auto e : res)
//    {
//        if (ed < e.first)
//        {
//            if (st != -2e9) tmp.push_back({ st, ed });
//            st = e.first, ed = e.second;
//        }
//        else ed = max(ed, e.second);
//    }
//
//    if (st != -2e9) tmp.push_back({ st, ed });
//
//    res = tmp;
//}
//
//int main()
//{
//    cin >> n;
//    while (n--)
//    {
//        int l, r;
//        cin >> l >> r;
//        lr.push_back({ l, r });
//    }
//
//    merge(lr);
//
//    cout << lr.size() << endl;
//
//    return 0;
//}

//
//#include <iostream>
//using namespace std;
//
//const int N = 100010;
//int idx, e[N], ne[N], m, head;
//
//void init()
//{
//    head = -1;
//    idx = 0;
//}
//
//void push_head(int x)
//{
//    e[idx] = x;
//    ne[idx] = head;
//    head = idx++;
//}
//
//void del(int k)
//{
//    ne[k] = ne[ne[k]];
//}
//
//void insert(int k, int x)
//{
//    e[idx] = x;
//    ne[idx] = ne[k];
//    ne[k] = idx++;
//}
//
//int main()
//{
//    cin >> m;
//
//    init();
//
//    while (m--)
//    {
//        int k, x;
//        string op;
//        cin >> op;
//
//        if (op == "H")
//        {
//            cin >> x;
//            push_head(x);
//        }
//        else if (op == "D")
//        {
//            cin >> k;
//            if (k == 0) head = ne[head];
//            else del(k - 1);
//        }
//        else
//        {
//            cin >> k >> x;
//            insert(k - 1, x);
//        }
//    }
//
//    for (int i = head; i != -1; i = ne[i]) cout << e[i] << ' ';
//    cout << endl;
//
//    return 0;
//}
//
// 
// 
// 
//#include <iostream>
//using namespace std;
//
//const int N = 100010;
//int r[N], l[N], e[N], idx, m;
//
//void init()
//{
//    r[0] = 1;
//    l[1] = 0;
//    idx = 2;
//}
//
//void pushL(int x)
//{
//    e[idx] = x;
//    r[idx] = r[0];
//    l[r[0]] = idx;
//    r[0] = idx;
//    l[idx] = 0;
//    idx++;
//}
//
//void pushR(int x)
//{
//    e[idx] = x;
//    l[idx] = l[1];
//    r[l[1]] = idx;
//    l[1] = idx;
//    r[idx] = 1;
//    idx++;
//}
//
//void del(int k)
//{
//    r[l[k]] = r[k];
//    l[r[k]] = l[k];
//}
//
//void push(int k, int x)
//{
//    e[idx] = x;
//    r[idx] = r[k];
//    l[r[k]] = idx;
//    r[k] = idx;
//    l[idx] = k;
//    idx++;
//}
//
//int main()
//{
//    cin >> m;
//
//    init();
//
//    while (m--)
//    {
//        string op;
//        int k, x;
//        cin >> op;
//
//        if (op == "L")
//        {
//            cin >> x;
//            pushL(x);
//        }
//        else if (op == "R")
//        {
//            cin >> x;
//            pushR(x);
//        }
//        else if (op == "D")
//        {
//            cin >> k;
//            del(k + 1);
//        }
//        else if (op == "IL")
//        {
//            cin >> k >> x;
//            push(l[k + 1], x);
//        }
//        else
//        {
//            cin >> k >> x;
//            push(k + 1, x);
//        }
//    }
//
//    for (int i = r[0]; i != 1; i = r[i]) cout << e[i] << ' ';
//    cout << endl;
//
//    return 0;
//}

//
//#include <iostream>
//using namespace std;
//
//const int N = 100010;
//int tt, st[N], n;
//
//int main()
//{
//    cin >> n;
//
//    while (n--)
//    {
//        string op;
//        cin >> op;
//        if (op == "push")
//        {
//            int x;
//            cin >> x;
//            st[tt++] = x;
//        }
//        else if (op == "pop") tt--;
//        else if (op == "empty")
//        {
//            if (tt) cout << "NO" << endl;
//            else cout << "YES" << endl;
//        }
//        else
//        {
//            cout << st[tt - 1] << endl;
//        }
//    }
//
//    return 0;
//}

//
//#include <iostream>
//using namespace std;
//
//const int N = 100010;
//int hh, tt, q[N], n;
//
//int main()
//{
//    cin >> n;
//
//    while (n--)
//    {
//        string op;
//        cin >> op;
//        if (op == "push")
//        {
//            int x;
//            cin >> x;
//            q[tt++] = x;
//        }
//        else if (op == "pop") hh++;
//        else if (op == "empty")
//        {
//            if (hh == tt) cout << "YES" << endl;
//            else cout << "NO" << endl;
//        }
//        else cout << q[hh] << endl;
//    }
//
//    return 0;
//}

